﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
/*
* @param n int整型 最大位数
* @return int整型一维数组
* @return int* returnSize 返回数组行数
*/

//static int arr[100001];
//int* printNumbers(int n, int* returnSize) {
//    // write code here
//    switch (n)
//    {
//    case 1:
//        n = 9;
//        break;
//    case 2:
//        n = 99;
//        break;
//    case 3:
//        n = 999;
//        break;
//    case 4:
//        n = 9999;
//        break;
//    case 5:
//        n = 99999;
//        break;
//    }
//    int i = 0;
//    for (i = 1; i <= n; i++)
//    {
//        arr[i - 1] = i;
//    }
//    *returnSize = i - 1;//题目要求参数返回的元素个数
//    return arr;//题目要求返回的列表(数组)
//}

//根据输入的日期，计算是这一年的第几天。
//保证年份为4位数且日期合法。
//进阶：时间复杂度：O(n) O(n) ，空间复杂度：O(1) O(1)
//输入描述：
//输入一行，每行空格分割，分别是年，月，日
//输出描述：
//输出是这一年的第几天

//int main()
//{
//	int year = 0;
//	int month = 0;
//	int day = 0;
//	int arr[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//	int leap_year = 0;
//	int sum = 0;
//	brk:
//	scanf("%d %d %d", &year, &month, &day);
//	if (year < 1000 || month < 1 || month>12 || day < 1 || day>31)
//	{
//		goto brk;
//	}
//	if (month == 4 || month == 6 || month == 9 || month == 11)
//	{
//		if (day > 30)
//			goto brk;
//	}
//	if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0)//闰年时
//	{
//		leap_year = 1;
//		arr[2] = 29;
//	}
//	else//平年时
//	{
//		leap_year = 0;
//		arr[2] = 28;
//	}
//	if (month == 2)//2月 天份判断
//	{
//		if (leap_year == 1 && day > 29)
//		{
//			goto brk;
//		}
//		else if (day > 28)
//		{
//			goto brk;
//		}
//	}
//	for (int i = 1; i < month; i++)
//	{
//		sum += arr[i];
//	}
//	sum += day;
//
//	printf("%d", sum);
//	return 0;
//}

// 验证尼科彻斯定理，即：任何一个整数m的立方都可以写成m个连续奇数之和。
//例如：
//1 ^ 3 = 1
//2 ^ 3 = 3 + 5
//3 ^ 3 = 7 + 9 + 11
//4 ^ 3 = 13 + 15 + 17 + 19
//输入一个正整数m（m≤100），将m的立方写成m个连续奇数之和的形式输出。
//数据范围：1≤m≤100

//#include<stdio.h>
//#define NUM 100 //数组大小
//int main()
//{
//	int arr[NUM] = { 0 };
//	int i = 0;
//	int j = 0;
//	for (i = 0, j = 1; i < NUM; i++, j += 2)//存放30个奇数的数组
//	{
//		arr[i] = j;
//	}
//	int input = 0;
//	scanf("%d", &input);
//	for (i = 0; i < NUM - input; i++)
//	{
//		int sum = arr[i];
//		for (j = 1; j < input; j++)
//		{
//			if (i + j >= NUM)//防止越界访问
//			{
//				printf("超出范围!程序终止");
//				return 0;
//			}
//			sum += arr[i + j];
//		}
//		if (sum == input * input * input)
//		{
//			printf("%d+", arr[i]);
//			for (j = 1; j < input; j++)
//			{
//				printf("%d", arr[i + j]);
//				if (j != input - 1)
//					printf("+");
//			}
//		}
//	}
//	return 0;
//}

//--------------------
//|                  |
//|       优化       |
//|                  |
//--------------------
//上面的代码有明显的问题  当输入的m比较大时,要让数组变得更大才行
//效率低下,内存占用大
//不过我们知道了一个规律, 4^3  是从第 3+2+1 个奇数开始往后加4个
//                        n^3  是从第 n-1+n-2+n+3……1 个奇数开始往后加n个
//#include<stdio.h>
//int main()
//{
//	int input = 0;
//	scanf("%d", &input);
//	int n = 0;//从第几个奇数开始往后加
//	int num = 0;//1到n-1
//	for (num = 1; num < input; num++)
//	{
//		n += num;
//	}
//	num = 1;
//	for (int i = 0; i < n; i++)//把用num存放 第n个奇数
//	{
//		num += 2;
//	}
//	for (int i = 0; i < input; i++)//从第n个奇数打印
//	{
//		printf("%d", num);
//		num += 2;
//		if (i != input - 1)
//			printf("+");
//	}
//	return 0;
//}

// 等差数列 2，5，8，11，14。。。。
//（从 2 开始的 3 为公差的等差数列）
//输出求等差数列前n项和
//数据范围： 1≤n≤1000 1≤n≤1000
//#include<stdio.h>
//int main()
//{
//	int input = 0;
//	scanf("%d", &input);
//	int end = 0;
//	int num = input;
//	for (end = 2; num - 1 > 0; num--)//因为end赋值为2 已经算一个了,所以num减一
//	{
//		end += 3;
//	}
//	printf("%d", ((2 + end) * input) / 2);
//	return 0;
//}

//首先输入要输入的整数个数n，然后输入n个整数。输出为n个整数中负数的个数，
//和所有正整数的平均值，结果保留一位小数。
//0即不是正整数，也不是负数，不计入计算。如果没有正数，则平均值为0。
//数据范围： 1≤n ≤2000  ，输入的整数都满足 ∣val∣≤1000 
//输入描述：
//首先输入一个正整数n，
//然后输入n个整数。
//输出描述：
//输出负数的个数，和所有正整数的平均值。
//#include<stdio.h>
//int main()
//{
//	int arr[2000] = { 0 };
//	int input = 0;
//	scanf("%d", &input);
//	int i = 0;
//	for (i = 0; i < input; i++)
//		scanf("%d", &arr[i]);
//
//	double num_sum = 0;
//	int negative_sum = 0;
//	int zero = 0;
//	for (i = 0; i < input; i++)
//	{
//		if (arr[i] < 0)
//			negative_sum++;
//		else if (arr[i] == 0)
//			zero++;
//		else
//			num_sum += arr[i];
//	}
//	double mean = 0;
//	if (input == zero)
//		;
//	else
//		mean = num_sum / ((input - negative_sum - zero) * 1.0);
//	printf("%d %.1lf", negative_sum, mean);
//	return 0;
//}

//有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，
//即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，
//比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。
//数据范围：1≤n≤10000，数组中任意元素的值:0≤val≤10000
/* @param nums int整型一维数组
*  @param numsLen int nums数组长度
*  @return int整型
*/
//#include<stdio.h>
//int minNumberInRotateArray(int* nums, int numsLen) {
//	int Min = nums[0];
//	for (int i = 1; i < numsLen; i++)
//	{
//		if (Min > nums[i])
//			Min = nums[i];
//	}
//	return Min;
//}
//int main()
//{
//	int arr[20] = { 8,9,10,11,12,13,14,15,16,17,18,19,20,1,2,3,4,5,6,7 };
//	printf("%d", minNumberInRotateArray(arr, 20));
//	
//	return 0;
//}

//小明同学最近开发了一个网站，在用户注册账户的时候，需要设置账户的密码，
//为了加强账户的安全性，小明对密码强度有一定要求：
//1. 密码只能由大写字母，小写字母，数字构成；
//2. 密码不能以数字开头；
//3. 密码中至少出现大写字母，小写字母和数字这三种字符类型中的两种；
//4. 密码长度至少为8
//现在小明受到了n个密码，他想请你写程序判断这些密码中哪些是合适的，哪些是不合法的。
//#include<stdio.h>
//#include<string.h>
//int main()
//{
//	int input = 0;
//	char arr[300] = { 0 };
//	scanf("%d", &input);
//	
//	for (int i = 0; i < input; i++)
//	{
//		while (getchar() != '\n');
//		scanf("%[^\n]", &arr);
//		size_t len = strlen(arr);
//		if (len < 8 || (arr[0] >= '0' && arr[0] <= '9'))
//		{
//			printf("NO\n");
//			goto END;
//		}
//		int num = 0;
//		int CH = 0;
//		int ch = 0;
//		for (int i = 0; i < len; i++)
//		{
//			if (arr[i] >= '0' && arr[i] <= '9')
//				num = 1;
//			if (arr[i] > 'A' && arr[i] < 'Z')
//				CH = 1;
//			if (arr[i] > 'a' && arr[i] <= 'z')
//				ch = 1;
//			if (
//				arr[i] < '0' ||
//				(arr[i] > '9' && arr[i] < 'A') ||
//				(arr[i] > 'Z' && arr[i] < 'a') ||
//				arr[i]>'z'
//				)
//			{
//				printf("NO\n");
//				goto END;
//			}
//		}
//		if (num + CH + ch < 2)
//		{
//			printf("NO\n");
//			goto END;
//		}
//		printf("YES\n");
//	END:
//		;
//	}
//	return 0;
//}

//给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数
/* @param nums int整型一维数组
* @param numsLen int nums数组长度
* @param k int整型
* @return int整型
*/
//int GetNumberOfK(int* nums, int numsLen, int k) {
//    if (numsLen <= 0)
//        return 0;
//    int left = 0;
//    int right = numsLen - 1;
//    int cont_k = 0;//存放k的坐标
//    while (left != right)//快速找到k
//    {
//        int middle = (left + right) / 2;
//        if (nums[middle] > k)
//            right = middle - 1;
//        else if (nums[middle] < k)
//            left = middle + 1;
//        else
//        {
//            cont_k = middle;
//            break;
//        }
//    }
//    if (nums[cont_k] != k)//判断数组中有没有k
//        return 0;
//
//    left = cont_k - 1, right = cont_k + 1;
//    int cont_left = 0;//当前k位置 左边有多少个相同的k
//    int cont_right = 0;//当前k位置 右边有多少个相同的k
//    while (nums[left--] == nums[cont_k])
//        cont_left++;
//    while (nums[right++] == nums[cont_k])
//        cont_right++;
//    return cont_left + cont_right + 1;
//}

//整数转换。编写一个函数，确定需要改变几个位才能将整数A转成整数B。
//示例1:
//输入：A = 29 （或者0b11101）, B = 15（或者0b01111）
//输出：2
//int convertInteger(int A, int B) {
//	int cont = A ^ B;//二级制有几个不同的地方
//	int sum = 0;
//	for (int i = 0; i < 32; i++)
//	{
//		if ((cont >> i) & 1 == 1)//判断最后一位是不是一
//			sum++;
//	}
//	return sum;
//}


//给你一个整数数组 nums ，其中总是存在 唯一的 一个最大整数 。
//请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。
//如果是，则返回 最大元素的下标 ，否则返回 - 1 。
//#include<stdio.h>
//int dominantIndex(int* nums, int numsSize) {
//	int big = nums[0];
//	for (int i = 0; i < numsSize; i++)
//	{
//		if (big < nums[i])
//			big = nums[i];
//	}
//	int big_2 = nums[0];
//	if (big_2 == big && numsSize > 1)//给第二大的值赋值,防止赋到了最大值
//		big_2 = nums[1];
//
//	for (int i = 0; i < numsSize; i++)
//	{
//		if (big_2 < nums[i] && nums[i] != big)
//			big_2 = nums[i];
//	}
//	if (big >= (big_2 * 2))
//	{
//		for (int i = 0; i < numsSize; i++)
//		{
//			if (big == nums[i])
//				return i;
//		}
//	}
//	else
//		return -1;
//}
//int main()
//{
//	int arr[2] = { 1,0 };
//	printf("%d", dominantIndex(arr, 2));
//	return 0;
//}

//给定两个数组 nums1 和 nums2 ，返回 它们的交集 。
//输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 
//int compar(const void* p1, const void* p2)
//{
//	return *(int*)p1 - *(int*)p2;
//}
//int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
//	qsort(nums1, nums1Size, sizeof(int), compar);
//	qsort(nums2, nums2Size, sizeof(int), compar);
//	int small = nums1Size < nums2Size ? nums1Size : nums2Size;
//	int* P = malloc(small * sizeof(int));
//	int cont = nums1[0] + 1;//存放重复的数,防止再次遍历  加一是为了防止跟第一个相同
//	int cont_2 = 0;//记录数组2的下一次从哪访问
//	int cont_3 = 0;//记录返回数组下一个坐标
//	int sum = 0;//返回的数组中一共有多少个元素
//	for (int i = 0; i < nums1Size; i++)
//	{
//		if (cont == nums1[i])
//			continue;
//		cont = nums1[i];
//		for (int j = cont_2; j < nums2Size; j++)
//		{
//			if (cont == nums2[j])
//			{
//				P[cont_3++] = nums1[i];
//				sum++;
//				cont_2 = j + 1;//记录下次开始遍历数组2的下标
//				for (int q = j + 1; q < nums2Size; q++)//特殊情况,如果数组2后面跟当前相同
//				{//那么下次开始遍历的数组下标自增
//					if (cont == nums2[q])
//						cont_2++;
//					else
//						break;
//				}
//				break;
//			}
//		}
//	}
//	*returnSize = sum;
//	return P;
//}

// Lily上课时使用字母数字图片教小朋友们学习英语单词，
//每次都需要把这些图片按照大小（ASCII码值从小到大）排列收好。请大家给Lily帮忙，通过代码解决。
//Lily使用的图片使用字符"A"到"Z"、"a"到"z"、"0"到"9"表示。
//数据范围：每组输入的字符串长度满足 1≤n≤1000 1≤n≤1000
// 
//输入描述：
//一行，一个字符串，字符串中的每个字符表示一张Lily使用的图片。
//输出描述：
//Lily的所有图片按照从小到大的顺序输出
//#include<stdio.h>
//#include<string.h>
//int main()
//{
//	char arr[1001] = { 0 };
//	gets(arr);
//	int len = strlen(arr);
//	for (int i = 0; i < len; i++)
//	{
//		for (int j = i + 1; j < len; j++)
//		{
//			if (arr[i] > arr[j])
//			{
//				char cont = arr[i];
//				arr[i] = arr[j];
//				arr[j] = cont;
//			}
//		}
//	}
//	puts(arr);
//	return 0;
//}


//给你一个整数数组 nums ，请计算数组的 中心下标 。
//数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
//如果中心下标位于数组最左端，那么左侧数之和视为 0 ，
//因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

//如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，
//int nums_left(int* nums, int n)//返回坐标左边元素和
//{
//	if (n == 0)
//		return 0;
//	int sum = 0;
//	for (int i = 0; i < n; i++)
//	{
//		sum += nums[i];
//	}
//	return sum;
//}
//int nums_right(int* nums, int n, int numsSize)//返回坐标右边元素和
//{
//	if (n == numsSize - 1)
//		return 0;
//	int sum = 0;
//	for (int i = n + 1; i < numsSize; i++)
//	{
//		sum += nums[i];
//	}
//	return sum;
//}
//int pivotIndex(int* nums, int numsSize) {
//	for (int i = 0; i < numsSize; i++)
//	{
//		if (nums_left(nums, i) == nums_right(nums, i, numsSize))
//			return i;
//	}
//	return -1;
//}
//编写一个函数，计算字符串中含有的不同字符的个数。
//字符在 ASCII 码范围内( 0~127 ，包括 0 和 127 )，换行表示结束符，
//不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次
//例如，对于字符串 abaca 而言，有 a、b、c 三种不同的字符，因此输出 3
//#include<stdio.h>
//#include<string.h>
//int main()
//{
//	char arr[128];//记录ASCII码0-127是否重复
//	int i = 0;
//	for (i = 0; i < 128; i++)
//		arr[i] = 1;
//	char input[501];
//	i = 0;
//	scanf("%s", &input[i++]);
//	int len = strlen(input);
//	int sum = 0;
//	for (i = 0; i < len; i++)
//	{
//		if (input[i] >= 0 && input[i] <= 127 && arr[input[i]])
//		{
//			arr[input[i]] = 0;
//			sum++;
//		}
//	}
//	printf("%d", sum);
//	return 0;
//}

//给定一个大小为 n 的数组 nums ，返回其中的多数元素。
//多数元素是指在数组中 [ 出现次数 ]  大于 [ n / 2 ] 的元素。
//你可以假设数组是非空的，并且给定的数组总是存在多数元素。

//思路: 出现次数大于数组元素个数的一半,那么 多数元素 和 其他元素 相互抵消后剩下的必定是多数元素
//int majorityElement(int* nums, int numsSize) {
//	int candidate = nums[0];//被投票的对象
//	int cont = 1;//票数
//	for (int i = 1; i < numsSize; i++)
//	{
//		if (candidate == nums[i])
//			cont++;
//		else
//		{
//			cont--;
//			if (cont == 0)//当票数没有时,则更改被投票的对象
//			{
//				candidate = nums[i];
//				cont = 1;//当更改投票对象时,也要重新赋值票数
//			}
//		}
//	}
//	return candidate;
//}

//自除数 是指可以被它包含的每一位数整除的数。
//例如，128 是一个 自除数 ，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
//自除数 不允许包含 0 。
//给定两个整数 left 和 right ，返回一个列表，列表的元素是范围[left, right] 内所有的 自除数 。
//#include<stdlib.h>
//int num(int n)
//{
//	int cont = 0;//每一位
//	int cont_n = n;
//	while (cont_n)
//	{
//		cont = cont_n % 10;
//		if (cont != 0 && n % cont == 0)
//		{
//			;
//		}
//		else
//			return 0;
//		cont_n /= 10;
//	}
//	return n;
//}
//int* selfDividingNumbers(int left, int right, int* returnSize) {
//	int cont = right - left + 1;
//	int* p = (int*)malloc(cont * sizeof(int));
//	int i = 0;
//	for (int j = left; j <= right; j++)
//	{
//		if (num(j))
//		{
//			p[i++] = num(j);
//		}
//	}
//	*returnSize = i;
//	return p;
//}

//给你一个整数数组 nums，返回 数组 answer ，
//其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
//题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
//请不要使用除法，且在 O(n) 时间复杂度内完成此题。

//输入: nums = [1, 2, 3, 4]
//输出 : [24, 12, 8, 6]

//输入 : nums = [-1, 1, 0, -3, 3]
//输出 : [0, 0, 9, 0, 0]
//#include<stdlib.h>
//int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
//    //除自身的乘积的的值 等于 左乘积 *  右乘积
//    int* leftPro = (int*)malloc(sizeof(int) * numsSize);
//    int* rightPro = (int*)malloc(sizeof(int) * numsSize);
//
//    //左乘积
//    leftPro[0] = 1;
//    for (int i = 1; i < numsSize; i++)
//    {
//        leftPro[i] = leftPro[i - 1] * nums[i - 1];
//    }
//    //右乘积
//    rightPro[numsSize - 1] = 1;
//    for (int i = numsSize - 1 - 1; i >= 0; i--)
//    {
//        rightPro[i] = rightPro[i + 1] * nums[i + 1];
//    }
//
//    *returnSize = numsSize;
//    int* returnNums = (int*)malloc(sizeof(int) * numsSize);
//    for (int i = 0; i < numsSize; i++)
//    {
//        returnNums[i] = leftPro[i] * rightPro[i];
//    }
//    return returnNums;
//}
// 写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
//数据范围：两个数都满足 −10≤n≤1000−10≤n≤1000
/* @param num1 int整型
* @param num2 int整型
* @return int整型
*/
//int Add(int num1, int num2) {
//    // add表示进位值
//    int add = num2;
//    // sum表示总和      
//    int sum = num1;
//    // 当不再有进位的时候终止循环
//    while (add != 0) {
//        // 将每轮的无进位和与进位值做异或求和(把不进位的计算完成)
//        // 当 sum&add 为0时 也就是没有进位的了就终止循环
//        int temp = sum ^ add;
//        // 进位值是用与运算产生的(进位产生的值左移一位,并在下次进行不进位的计算)
//        add = (sum & add) << 1;
//        // 更新sum为新的和
//        sum = temp;
//    }
//    return sum;
//}

//给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。
//请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

//输入：nums = [4, 3, 2, 7, 8, 2, 3, 1]
//输出：[5, 6]

//输入：nums = [1, 1]
//输出：[2]
//int compar(const void* p1, const void* p2)
//{
//	return *(int*)p1 - *(int*)p2;
//}
//int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {
//	qsort(nums, numsSize, sizeof(int), compar);
//	int* P = malloc(sizeof(int) * numsSize);
//
//	int cont_coordinate = 0;//存储下次访问的数组下标
//	int cont_num = nums[0] - 1;//记录上一个数,防止重复
//	int sum = 0;//总数
//	int cont_P = 0;//记录P的下标
//	for (int n = 1; n <= numsSize; n++)//1-n
//	{
//		int have = 0;//1:数组中有n, 0:数组中没有n
//		for (int i = cont_coordinate; i < numsSize; i++)//数组元素
//		{
//
//			if (cont_num == nums[i])
//			{
//				cont_num == nums[i];
//				cont_coordinate = i + 1;
//				continue;
//			}
//			if (n == nums[i])
//			{
//				cont_num == nums[i];
//				cont_coordinate = i + 1;
//				have = 1;
//				break;
//			}
//		}
//		if (!have)
//		{
//			P[cont_P++] = n;
//			sum++;
//		}
//	}
//	*returnSize = sum;
//	return P;
//}
// 
// 
//------------------
//|                |
//|    ↓优化↓    |
//|                |
//------------------
//我们创建一个数组N, 输入的数组我们称为数组M
//思想:     创建一个numsSize大的数组N,存放每一个M数组的元素
//存放规则: 数组中的数,是哪个数就存到 数组N的哪个坐标上 存放为负数
//最后我们再次遍历一遍,然后累计出所有非负数,就是结果
//int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {
//	int* P = malloc(sizeof(int) * (numsSize + 1));
//	int* return_P = malloc(sizeof(int) * numsSize);
//	int cont_P = 0;
//	int sum = 0;
//
//	P[0] = -1;
//	for (int i = 1; i < numsSize; i++)
//	{
//		P[i] = 1;
//	}
//	for (int i = 0; i < numsSize; i++)
//	{
//		P[nums[i]] = -1;
//	}
//	for (int i = 1; i <= numsSize; i++)
//	{
//		if (P[i] != -1)
//		{
//			return_P[cont_P++] = i;
//			sum++;
//		}
//	}
//	*returnSize = sum;
//	return return_P;
//}


//给定一个二进制数组 nums ， 计算其中最大连续 1 的个数

//int findMaxConsecutiveOnes(int* nums, int numsSize) {
//	int sum = 0;
//	int cont = 0;
//	for (int i = 0; i < numsSize; i++)
//	{
//		if (nums[i] == 1)
//			cont++;
//		if (cont > sum)
//			sum = cont;
//		if (i == numsSize - 1 || nums[i + 1] != 1)
//			cont = 0;
//	}
//	return sum;
//}

/* 完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。
它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。
例如：28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1 + 2 + 4 + 7 + 14 = 28。
输入n，请输出n以内(含n)完全数的个数。
数据范围： 1≤n≤5×105 1≤n≤5×105

输入描述：
输入一个数字n

输出描述：
输出不超过n的完全数的个数*/
//#include<stdio.h>
//#include<math.h>
//int main()
//{
//	int left = 0;//左约数  例如 28 = 1 * 28 左约数是1
//	int right = 0;//右约数
//	int input = 0;//输入的范围
//	int cont = 0;//记录有几个数满足要求
//
//	scanf("%d", &input);
//	for (int i = 1; i <= input; i++)
//	{
//		int sum = 0;//约数和  
//		for (left = 2; left <= sqrt(i); left++)
//		{
//			if (i % left == 0)
//			{
//				right = i / left;
//				if (left == right)//如果两个约数相同,那么只取一个约数
//					sum += left;
//				else
//				{
//					sum += left;
//					sum += right;
//				}
//			}
//		}
//		if (i != 1)//除了1,因为1的本身是1,约数1不能要
//			sum++;//上面的求约数和,是从2开始的,又因题目不要数本身,所以每次结束后sum自增1
//		if (sum == i)
//			cont++;
//	}
//	printf("%d\n", cont);
//	return 0;
//}

/*输入一个整数，将这个整数以字符串的形式逆序输出
程序不考虑负数的情况，若数字含有0，则逆序形式也含有0，如输入为100，则输出为001

输入描述：
输入一个int整数

输出描述：
将这个整数以字符串的形式逆序输出*/
//#include<stdio.h>
//int main()
//{
//	int input = 0;
//	scanf("%d", &input);
//	if (!input)
//	{
//		printf("%c", '0');
//		return 0;
//	}
//	while (input)
//	{
//		printf("%c", input % 10 + 48);
//		input /= 10;
//	}
//	return 0;
//}

/* 对字符串中的所有单词进行倒排。
说明：
1、构成单词的字符只有26个大写或小写英文字母；
2、非构成单词的字符均视为单词间隔符；
3、要求倒排后的单词间隔符以一个空格表示；如果原字符串中相邻单词间有多个间隔符时，倒排转换后也只允许出现一个空格间隔符；
4、每个单词最长20个字母；
数据范围：字符串长度满足 1≤n≤10000 1≤n≤10000
输入描述：

输入一行，表示用来倒排的句子
输出描述：

输出句子的倒排结果*/
//#include<stdio.h>
//#include<string.h>
//#include<stdlib.h>
//void reverse(char* arr,int left, int right)
//{
//	while (left < right)
//	{
//		char cont = arr[left];
//		arr[left] = arr[right];
//		arr[right] = cont;
//		left++;
//		right--;
//	}
//}
//int main()
//{
//	char input[10001] = { 0 };
//	scanf("%[^\n]c", &input);
//	int len = strlen(input);
//
//	char* put = malloc(sizeof(char) * (len + 1));
//	int j = 0;//输出数组的下标
//	int cont = 0;//记录是否为非字母字符
//
//	for (int i = len - 1; i >= 0; i--)
//	{
//		if (input[i] >= 'A' && input[i] <= 'Z' ||
//			input[i] >= 'a' && input[i] <= 'z')
//		{
//			put[j++] = input[i];
//			cont = 0;
//		}
//		else if (cont)//重复是非字母字符时
//			continue;
//		else
//		{
//			put[j++] = ' ';
//			cont = 1;
//		}
//	}
//	put[j] = ' ';//最后一个赋值为空格,为下面的遇到空格就逆序做铺垫
//	int left = 0;
//	int right = 1;
//	while (left < right)
//	{
//		for (int i = 0; i < len + 1; i++)//为了查找最后一个空格,而进行逆序,多访问一个元素
//		{
//			if (put[i] == ' ')
//			{
//				right = i - 1;
//				reverse(put, left, right);
//				left = i + 1;
//			}
//		}
//	}
//	put[j] = '\0';//给原来最后一个元素重新赋值\0表示结束
//	printf("%s", put);
//	free(put);
//	return 0;
//}
// 改版:  全部倒排
//int main()
//{
//	char input[10001] = { 0 };
//	scanf("%[^\n]c", &input);
//	int len = strlen(input);
//	char* put = malloc(sizeof(char) * (len + 1));
//	int j = 0;//输出数组的下标
//	int cont = 0;//记录是否为非字母字符
//
//	for (int i = len - 1; i >= 0; i--)
//	{
//		if (input[i] >= 'A' && input[i] <= 'Z' ||
//			input[i] >= 'a' && input[i] <= 'z')
//		{
//			put[j++] = input[i];
//			cont = 0;
//		}
//		else if (cont)//重复是非字母字符时
//			continue;
//		else
//		{
//			put[j++] = ' ';
//			cont = 1;
//		}
//	}
//	put[j] = '\0';
//	printf("%s", put);
//	free(put);
//	return 0;
//}

/* 有一种兔子，从出生后第3个月起每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子。
例子：假设一只兔子第3个月出生，那么它第5个月开始会每个月生一只兔子。
一月的时候有一只兔子，假如兔子都不死，问第n个月的兔子总数为多少？
数据范围：输入满足 1≤n≤31 1≤n≤31

输入描述：
输入一个int型整数表示第n个月

输出描述：
输出对应的兔子总数.*/
/*兔子长到第三月,在第三月就开始生了*/
//#include<stdio.h>
//int main()
//{
//	int input = 0;
//	scanf("%d", &input);
//	int rabbit_3 = 0;//满足三月大的兔子
//	int rabbit_2 = 0;//满足两月大的兔子
//	int rabbit_1 = 1;//兔宝宝
//	for (int i = 1; i < input; i++)//从第二月开始
//	{
//		rabbit_3 += rabbit_2;//两月兔子->三月兔子
//		rabbit_2 = rabbit_1;//一月兔子->两月兔子
//		rabbit_1 = rabbit_3;//三月兔子生了一倍一月兔子
//	}
//	printf("%d", rabbit_3 + rabbit_2 + rabbit_3);
//	return 0;
//}

/* 数列的定义如下：数列的第一项为n，以后各项为前一项的平方根，求数列的前m项的和。
输入描述：
输入数据有多组，每组占一行，由两个整数n（n < 10000）和m(m < 1000)组成，n和m的含义如前所述。
输出描述：
对于每组输入数据，输出该数列的和，每个测试实例占一行，要求精度保留2位小数。

示例1
输入：
81 4       (求第一项为81的数列,前4项和)
2 2        (求第一项为2的数列,前2项和)

输出：
94.73
3.41*/
//#include<stdio.h>
//#include<math.h>
//int main()
//{
//	double n = 0, m = 0;
//	while (scanf("%lf %lf", &n, &m) != EOF)
//	{
//		double sum = n;
//		for (int i = 0; i < m - 1; i++)
//		{
//			n = sqrt(n);
//			sum += n;
//		}
//		printf("%.2lf\n", sum);
//	}
//	return 0;
//}

/*珠玑妙算游戏（the game of master mind）的玩法如下。

计算机有4个槽，每个槽放一个球，颜色可能是红色（R）、黄色（Y）、绿色（G）或蓝色（B）。
例如，计算机可能有RGGB 4种（槽1为红色，槽2、3为绿色，槽4为蓝色）。
作为用户，你试图猜出颜色组合。打个比方，你可能会猜YRGB。要是猜对某个槽的颜色，
则算一次“猜中”；要是只猜对颜色但槽位猜错了，则算一次“伪猜中”。
注意，“猜中”不能算入“伪猜中”。
给定一种颜色组合solution和一个猜测guess，编写一个方法，
返回猜中和伪猜中的次数answer，其中answer[0]为猜中的次数，answer[1]为伪猜中的次数。

示例：
输入： solution="RGBY",guess="GGRR"
输出： [1,1]
解释： 猜中1次，伪猜中1次。
*/
//#include<stdlib.h>
//int* masterMind(char* solution, char* guess, int* returnSize) {
//	int CaiZhong = 0;
//	int WeiCaiZhong = 0;
//	int* returnARR = malloc(sizeof(int) * 2);
//	*returnSize = 2;
//	int R = 0, Y = 0, G = 0, B = 0;
//	for (int i = 0; i < 4; i++)
//	{
//		if (solution[i] == guess[i])
//		{
//			CaiZhong++;
//		}
//		else if (solution[i] == 'R')
//			R++;
//		else if (solution[i] == 'Y')
//			Y++;
//		else if (solution[i] == 'G')
//			G++;
//		else if (solution[i] == 'B')
//			B++;
//	}
//	for (int i = 0; i < 4; i++)
//	{
//		if (solution[i] == guess[i])//猜中的不能算是伪猜中的
//		{
//			;
//		}
//		else if (guess[i] == 'R' && R > 0)
//		{
//			R--;
//			WeiCaiZhong++;
//		}
//		else if (guess[i] == 'Y' && Y > 0)
//		{
//			Y--;
//			WeiCaiZhong++;
//		}
//		else if (guess[i] == 'G' && G > 0)
//		{
//			G--;
//			WeiCaiZhong++;
//		}
//		else if (guess[i] == 'B' && B > 0)
//		{
//			B--;
//			WeiCaiZhong++;
//		}
//	}
//
//	returnARR[0] = CaiZhong;
//	returnARR[1] = WeiCaiZhong;
//	return returnARR;
//}

/* 给出一个整型数组 numbers 和一个目标值 target，
请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。
（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）
输入：
[3, 2, 4], 6
返回值：
[2, 3]
说明：
因为 2 + 4 = 6 ，而 2的下标为2 ， 4的下标为3 ，又因为 下标2 < 下标3 ，所以返回[2, 3]*/

/*
* @param numbers int整型一维数组
* @param numbersLen int numbers数组长度
* @param target int整型*/
//int* twoSum(int* numbers, int numbersLen, int target, int* returnSize) {
//	int* P = malloc(sizeof(int) * 2);
//	*returnSize = 2;
//	for (int i = 0; i < numbersLen; i++)
//	{
//		if (numbers[i] <= target)
//		{
//			for (int j = i + 1; j < numbersLen; j++)
//			{
//				if (numbers[i] + numbers[j] == target && P != NULL)
//				{
//					P[0] = i + 1;
//					P[1] = j + 1;
//					return P;
//				}
//			}
//		}
//	}
//	return 0;
//}

/*现在有一个长度为 n 的正整数序列，其中只有一种数值出现了奇数次*/
/*其他数值均出现偶数次，请你找出那个出现奇数次的数值。
数据范围：1≤n≤2×106 1≤n≤2×106

输入描述：
第一行：一个整数n，表示序列的长度。第二行：n个正整数ai，两个数中间以空格隔开。
输出描述：
一个数，即在序列中唯一出现奇数次的数值。
示例1
输入：
5
2 1 2 3 1

输出：
3     
*/
//#include<stdio.h>
//#include<stdlib.h>
//int main() 
//{
//    int input = 0;
//    scanf("%d", &input);
//    int* P = malloc(sizeof(int) * input);
//    int i = 0;
//    for (i = 0; i < input; i++)
//        scanf("%d", P + i);
//    for (i = 0; i < input; i++)
//    {
//        int cont = P[i];//当前查询的值
//        int sum = 0;//在数组中出现过的次数
//        for (int j = 0, q = input - 1; j < q; j++, q--)
//        {
//            if (cont == P[j])
//                sum++;
//            if (cont == P[q])
//                sum++;
//        }
//        if (sum % 2 == 1)
//        {
//            printf("%d", cont);
//            return 0;
//        }
//    }
//    return 0;
//}
/*
-----------
|  优化   |
-----------
相同的数进行异或那么就会消失, 我们可以遍历一遍, 
把数组的每一个元素都进行累积的异或, 这样可以消除掉所有的偶数, 
并且奇数是 2 * n + 1的形式, 其中2* n会被异或掉, 只剩下1(也就是奇数本身)
*/
//#include<stdio.h>
//int main()
//{
//	int n = 0;
//	int end = 0;
//	scanf("%d", &n);
//	for (int i = 0; i < n; i++)
//	{
//		int input = 0;
//		scanf("%d", &input);//获取数组每一个元素
//		end ^= input;//让数组所有元素进行异或运算
//	}
//	printf("%d", end);
//	return 0;
//}

/* 给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
2.假设 nums[-1] = nums[n] = −∞−∞
3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
4.你可以使用O(logN)的时间复杂度实现此问题吗？ 

输入：
[2,4,1,2,7,8,4]

返回值：
1

说明：
4和8都是峰值元素，返回4的索引1或者8的索引5都可以     */
/* @param nums int整型一维数组
* @param numsLen int nums数组长度
* @return int整型
*/
//int findPeakElement(int* nums, int numsLen) {
//	if (nums[0] > nums[1])//开头
//		return 0;
//	if (nums[numsLen - 2] < nums[numsLen - 1])//结尾
//		return numsLen - 1;
//	int cont = nums[1];
//	for (int i = 2; i < numsLen; i++)
//	{
//		if (nums[i] > cont)//判断前元素是否为峰值
//			cont = nums[i];
//		else
//			return i - 1;//返回前面元素坐标
//	}
//	return 0;
//}

/* 牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。
但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。

牛牛希望你能帮他计算一共有多少个可能的数对。
输入描述：
输入包括两个正整数n,k(1 <= n <= 10^5, 0 <= k <= n - 1)。
输出描述：
对于每个测试用例, 输出一个正整数表示可能的数对数量。
示例1
输入：
5 2

输出：
7

说明：
满足条件的数对有(2,3),(2,4),(2,5),(3,4),(3,5),(4,5),(5,3)*/
//#include<stdio.h>
//int main()
//{
//	int n = 0;//均不大于n
//	int k = 0;//余数大于等于k
//	scanf("%d %d", &n, &k);
//	int x = 0, y = 0;
//	int sum = 0;
//	for (x = 1; x <= n; x++)
//	{
//		for (y = 1; y <= n; y++)
//		{
//			if (x % y >= k)
//				sum++;
//		}
//	}
//	printf("%d", sum);
//	return 0;
//}

/* 输入一个字符串和一个整数 k ，截取字符串的前k个字符并输出
数据范围：字符串长度满足 1≤n≤1000 1≤n≤1000  ， 1≤k≤n 1≤k≤n 

输入描述：
1.输入待截取的字符串
2.输入一个正整数k，代表截取的长度

输出描述：
截取后的字符串*/
//#include<stdio.h>
//int main()
//{
//	char arr[1001];
//	scanf("%[^\n]", arr);
//	int k = 0;
//	scanf("%d", &k);
//	arr[k] = '\0';
//	printf("%s", arr);
//	return 0;
//}

/*集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，
导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，
导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

示例 1：
输入：nums = [1,2,2,4]
输出：[2,3]

***说明: 重复的是2   3是丢失的数字  因为 1 2 2 4  中并没有3 
示例 2：
输入：nums = [1,1]
输出：[1,2]

元素个数>=2
*/
int compar(const void* p1, const void* p2)
{
	return *(int*)p1 - *(int*)p2;
}
int* findErrorNums(int* nums, int numsSize, int* returnSize) {
	int* P = malloc(sizeof(int) * 2);//要返回的数组
	*returnSize = 2;
	qsort(nums, numsSize, sizeof(int), compar);//* * * 数组排序
	int cont = nums[0];//记录重复的
	int repeat_Yes = 1;//是否还要找重复的数字
	int deletion_Yes = 1;//是否还要找丢失的数字
	for (int i = 1; i < numsSize; i++)
	{
		if (cont == nums[i])//寻找重复的
		{
			P[0] = cont;
			repeat_Yes = 0;
		}
		else
			cont = nums[i];

		if (nums[i] - nums[i - 1] == 2)//寻找丢失的部分
		{
			P[1] = nums[i] - 1;
			deletion_Yes = 0;
		}
		if (!repeat_Yes && !deletion_Yes)
			return P;
	}
	if (deletion_Yes)//(:特殊情况 如果是数组元素比较少的  例如2个 3个
	{
		if (nums[0] != 1)
			P[1] = 1;
		else
			P[1] = nums[numsSize - 1] + 1;
	}
	return P;
}
